1. Technical Field of the Invention
The present invention relates to computer graphics, and more particular, to graphics processing methods, apparatus and computer program products.
2. Description of Related Art
Mobile phones are used all over the world. As they typically are equipped with displays, it is also possible to render images on these devices. It is very likely that this makes the mobile phone the most widespread rendering platform today. However, this type of rendering has mostly been limited to very simple two-dimensional graphics, and it is only recently that three-dimensional graphics has seen the light in this context. Increased interest in mobile graphics can be seen in the activities of upcoming standards, such as Java Specification Request 184 (see, e.g., www.jcp.org) and OpenGL ES for embedded systems (see, e.g., www.khronos.org). Applications that are likely to use three-dimensional graphics include man-machine interfaces (MMIs), screen savers, maps, animated messages, and, naturally, games.
Mobile phones inherently exhibit two characteristics that are drastically different from, for example, PC systems with graphics cards. First of all, they have very small displays, and second, they have very small amounts of resources for rendering. These characteristics will be briefly discussed next.
Existing mobile phones with color displays often have a resolution of [176-320]×[144-240], i.e., the displays are very small. The QCIF standard defines a resolution of 176×144, and the QVGA standard uses 320×240. While larger resolutions, such as 1024×768, will appear on mobile phones as well, it is quite likely that this only will be on the very high-end of mobile phones, and thus not available to most people. In addition to that, such large resolutions will probably consume more energy, which can decrease battery lifetime. Therefore, it can be expected that the smaller resolutions, such as QCIF and QVGA, will dominate.
In terms of number of colors on the display, anything from 256 to 65,536 colors are common. In addition to small resolution, the user often holds the display close to the eyes, which makes the average eye-to-pixel angle large in comparison to that of a PC system. In conclusion, these display conditions imply that every pixel on a mobile phone should ultimately be rendered with higher quality than on a PC system. This is sometimes called the “inverse screen size rendering quality law.”
There are several reasons for a mobile phone to have small resources. Because they typically are powered by rechargeable batteries, any type of rendering should preferably use as little energy as possible. Moreover, battery technology typically does not improve at the rate of Moore's law. Also, external memory accesses are most often the operation in a computer system that uses the most energy. This means that bandwidth resources should be used with great care, and that peak bandwidth is extremely limited in the first place.
To keep costs per device low, mobile phones are generally equipped with very little memory, and little chip area is dedicated to graphics operations. Little available bandwidth, little amount of chip area, and small amounts of memory all help to keep the price per device low, but more importantly, these factors also, in the majority of cases, contribute to using less energy than a system with more resources. Typical examples of real mobile phone data is: 1) one or a half 32-bit memory access per clock cycle, 2) CPUs with 10-200 MHz, and 3) 1-16 MB of reasonably fast memory.
The real-time rendering of three-dimensional graphics has a number of appealing applications on mobile terminals, including games, man-machine interfaces, messaging and m-commerce. Because three-dimensional rendering typically is a computationally expensive task, dedicated hardware often must be built to reach sufficient performance. Innovative ways of lowering the complexity and bandwidth usage of this hardware architecture are thus of great importance.
In a large number of cases, a z-buffer (depth buffer) is used to resolve visibility. This is typically done because triangles can generally be drawn in any order. Therefore, the z-buffer stores a scaled distance from the eye to the triangle, and if a subsequent triangle is farther away than the contents of the z-buffer, then the color and the z-buffer are not overdrawn.
Still, this also implies that the graphics system is not very clever, as a pixel can be overdrawn several times. And even if a pixel is overwritten several times, only one geometric primitive (triangle) may be visible in the end. An analog is painting on a canvas, where the bottommost paint layers will be obscured by the frontmost paint layers. For a graphics system, the same holds, but with the exception that paint can be drawn in any order.
It is also important to realize that for a mobile platform, it is generally desirable that the bandwidth usage to main memory should be reduced as much as possible, because such memory accesses use up a significant portion of the energy, which typically is a scarce resource.
There are several graphics cards (NVIDIA Geforce3 and up, and ATI Radeon) that use a form of occlusion culling today. The screen is divided into, say, 8×8 regions (called tiles), and for each tile, the maximum of the z-values, zmax, in the z-buffer for that tile is stored in a cache-memory (fast and not energy-expensive). When triangles are rendered, all pixels are visited in a tile before turning to the next tile, and when a new tile is encountered the minimum z-value, zmin, on the triangle inside that tile is computed (or some cheaper less accurate method can be used to overestimate the minimum z-value). If zmin is larger than the tile's zmax, then that triangle that we currently render is occluded (obstructed), and we typically do not need to process that tile for that triangle further. If the tile is not occluded, then the pixels inside the tile are processed as usual, i.e., the pixels are tested for inclusion in the triangle, z-testing occurs, and texturing, etc.
U.S. Pat. No. 6,421,764 to Morein, “Method and apparatus for efficient clearing of memory”, (described in Akenine-Möller Tomas, and Eric Haines, Real-Time Rendering, 2nd edition, June 2002, pp. 694-697) describes a way for effective clearing of memory. Instead of clearing the z-buffer (for example), he sets a flag for each tile (e.g., a 8×8 region). Later, when that tile is accessed for the first time, reading of the pixels in that block can be avoided, and instead a “cleared value” is read from a fast on-chip memory since the flag is set. When the tile is written to for the first time, the flag is unset. This way, only a fraction of the memory may be touched during clearing, which can save energy and bandwidth.
It is generally desirable that the bandwidth usage to main memory be kept as low as possible, in order to get better performance and to save (battery) power. To interpolate texture (image) data, z-coordinates, etc., over the triangle, one may need to store several parameters, and the set of parameters for a particular pixel is called a context. This context can be updated when one moves to another pixel. As more contexts are used, the more expensive the solution in terms of gates in hardware can become.
It is generally desirable that the number of gates be kept as low as possible in order to get a cost-efficient solution. Some currently known methods to visit all the pixels in a tile before moving on to the next tile need 4 or 5 whole contexts (confer McCormack, Joel, and Robert McNamara, “Tiled Polygon Traversal Using Half-Plane Edge Functions”, Workshop on Graphics Hardware, pp. 15-22, August 2000, and also Kelleher, Brian, “Pixel Vision Architechture”, Digital Systems Research Center, no. 1998-013, October 1998). This may be too expensive for a mobile platform. It should also be noted that it is possible to use the z-max techniques, but a potential problem with these is that it may be expensive to update the z-max after a triangle has been rendered, because all z-values in the entire tile need to be read before z-max can be updated. Current solutions that use z-max solve this by reading the entire block of z-values. This is possible because they typically have much higher bandwidth to the main memory than a mobile platform has, and they can, thus, afford that type of solution.
In general, there has not been much published on low-cost architectures where the entire system is described. Two notable exceptions are Neon (described in McCormack, Joel, and Robert McNamara, “Tiled Polygon Traversal Using Half-Plane Edge Functions”, Workshop on Graphics Hardware, pp. 15-22, August 2000), and the Pixel Vision architecture (described in Kelleher, Brian, “Pixel Vision architecture”, Digital Systems Research Center, no. 1998-013, October 1998). Imagination Technologies has a system called MBX, and this architecture is tile-based, and therefore the z-buffer, back buffer, and stencil buffer only need to be the size of a tile, e.g., 32×16 pixels. This memory is often implemented in fast on-chip memory. Initially, one pass needs to sort all geometry into the tiles, and this requires memory and memory bandwidth as well. When this sorting is finished, the geometry in each tile is rasterized. During rasterization, visibility is first resolved, and then texturing and shading is performed only on visible fragments. This is called deferred shading. To keep rasterization of tiles going in parallel with tile sorting, two buffers per tile are needed. There is not much information on the MBX architecture, and therefore, it is not clear what the gains really are, besides the avoidance of memory for buffers. Is it quite obvious that this architecture gives savings in terms of energy. However, it has not been documented how much.
For rasterization of polygons with subpixel accuracy, one can use a modified Bresenham algorithm, as described in Lathrop, O., Kirk, D., and Voorhies, “Accurate rendering by subpixel addressing,” IEEE Computer Graphics and Applications 10, 5 (September 1990), pp. 45-53. An often used alternative is to use edge functions as described in Pineda, J., “A parallel algorithm for polygon rasterization,” Proceedings of SIGGRAPH 1988, ACM, pp. 17-20 (1988), where the region inside a triangle is described as the logical intersection of the positive half-spaces of the triangle edges. Then, different strategies can be used to find the pixels inside the triangle. This is called traversal. Depending on how efficient these strategies are, different number of contexts (interpolation parameters, etc) are required during traversal. Each context usually costs considerably in terms of gates.
FIG. 1 shows traversal of a triangle according to Pineda's zigzag traversal scheme. The pixels marked with light gray or dark gray are pixels that are touched by the traversal scheme. The pixels marked with dark gray are the ones that the traversal algorithm finds to be inside the triangle. The path that the zigzag traversal algorithm takes is shown as an arrowed path. Basically, the triangle is traversed right-to-left on the first scanline, until we are outside the triangle. Then we go one step up. If we are then inside the triangle, we need to continue in the same direction until we are outside the triangle. This is called backtracking. When we are outside the triangle, the traversal direction is reversed and we start rasterizing the current scanline, this time from left-to-right. When we get outside the triangle, we take another step up, and so it continues.
An example is shown in FIG. 1. On the bottom-most scanline, one pixel is set, but the next one to the left is outside the triangle. This means that we should go one step up. After this step, we are inside the triangle, and we must backtrack, i.e., continue to go left, until we are outside of the triangle. After one pixel we are outside the triangle, and we can reverse the traversal direction (from right-to-left to left-to-right) and start rasterizing the second scan line. We find two pixels that should be inside the triangle, and after this we are outside the triangle and must go one step up. This time we are already outside the triangle and we do not need to backtrack. Hence, we can reverse the traversal direction and start rasterizing the third scanline, and so it goes on.
Every time we encounter a pixel that is found to be inside the triangle, we need to find out whether or not we should draw it. Thus we calculate the z-value of the triangle in that point, here called z-tri (x,y), where (x,y) are the coordinates of the point. Then we fetch the z-value from the z-buffer for that pixel, called z-buf (x,y). If z-tri (x,y)>=z-buf (x,y), nothing happens. However, if z-tri (x,y)<z-buf (x,y), then we should draw the pixel, and also update the z-buffer with the z-tri (x,y) value. In pseudo code, it can look as follows:
calculate z-tri (x,y)fetch z-buf (x,y) from z-bufferif (z-tri (x,y) < z-buf (x,y)){write z-tri (x,y) to z-bufferwrite color in color-buffer}
Note that the if statement can be changed to an arbitrary depth test if (depthtest (z-tri(x,y), z-buf (x,y)). To increase the level of utilization of coherence, and for simple occlusion culling algorithms, graphics hardware often traverses the pixels that a triangle covers in a tiled fashion (see Kelleher, Brian, “Pixel Vision architecture”, Digital Systems Research Center, no. 1998-013, October 1998; McCormack, Joel, and Robert McNamara, “Tiled Polygon Traversal Using Half-Plane Edge Functions”, Workshop on Graphics Hardware, pp. 15-22, August 2000; U.S. Pat. No. 6,421,764 to Morein). This means that all pixels inside a tile, say an 8×8 region, are visited before moving on to another tile. Different traversal strategies are needed for this, and these cost in terms of numbers of contexts that must be stored. For example, McCormack and McNamara describe a tiled traversal algorithm that requires one more context than the corresponding non-tiled traversal. In total, they need four contexts for the tiled version.
The hierarchical z-buffer algorithm uses a z-pyramid, where each pixel in each level in the pyramid store the maximum of its four children's z-values (in the level below), as described in Greene, N., Kass, M., and Miller, G., “Hierarchical z-buffer visibility,” Proceedings of SIGGRAPH 1993, ACM, pp. 231-238 (1993); U.S. Pat. No. 5,600,763 and U.S. Pat. No. 5,579,455. Thus, at the tip of the pyramid, the maximum of all z-values over the entire screen is stored. This pyramid is used to perform occlusion culling. When rendering a group of geometry, the bounding volume of the group is scan-converted and tested against appropriate levels in the z-buffer to determine whether the group is visible. This algorithm is highly efficient when implemented in software, however, there still does not exist a full-blown hardware implementation. However, commodity graphics hardware often have a simpler form of occlusion culling. Morein, S., “ATI radeon Hyperz technology”, Workshop on Graphics Hardware, Hot3D Proceedings, ACM SIGGRAPH/Eurographics.Morein (2000) describes a technique, where each tile stores the maximum, zmax, of the z-values inside a tile, which can be e.g., 8×8 pixels. During traversal of a triangle, a test is performed when a new tile is visited that determines if the “smallest” z-value of the triangle is larger than zmax of the corresponding tile. If so, that tile is skipped, and otherwise that tile is rendered as usual. Note that, to update zmax, all the z-values of the tile must be read, which can be expensive.